package sliding_window

import (
	"math"
	"sort"
)

/*

给你一个长度为 n 的整数数组nums和 一个目标值target。请你从 nums 中选出三个整数，使它们的和与target最接近。
返回这三个数的和。
假定每组输入只存在恰好一个解

*/
func abs(x int) int {
	if x < 0 {
		return -1 * x
	}
	return x
}

// 暴力解法 O(n^3)
func threeSumClosest3(nums []int, target int) int {
	n, res, diff := len(nums), 0, math.MaxInt32
	for i := 0; i < n; i++ {
		for j := i + 1; j < n; j++ {
			for k := j + 1; k < n; k++ {
				if abs(nums[i]+nums[j]+nums[k]-target) < diff {
					diff = abs(nums[i] + nums[j] + nums[k] - target)
					res = nums[i] + nums[j] + nums[k]
				}
			}
		}
	}
	return res
}

func threeSumClosest2(nums []int, target int) int {
	n, res, diff := len(nums), 0, math.MaxInt32
	if n > 2 {
		// 排序
		sort.Ints(nums)
		for i := 0; i < n-2; i++ {
			//去重
			if i > 0 && nums[i] == nums[i-1] {
				continue
			}
			for j, k := i+1, n-1; j < k; {
				sum := nums[i] + nums[j] + nums[k]
				if abs(sum-target) < diff {
					res, diff = sum, abs(sum-target)
				}
				if sum == target {
					return res
				} else if sum > target {
					k--
				} else {
					j++
				}
			}
		}
	}
	return res
}

// threeSumClosest 官方题解  O(n^2)
func threeSumClosest(nums []int, target int) int {

	//排序
	sort.Ints(nums)
	var n, best = len(nums), math.MaxInt32

	//根据差值的绝对值来更新答案
	update := func(cur int) {
		if abs(cur-target) < abs(best-target) {
			best = cur
		}
	}

	//枚举A
	for i := 0; i < n; i++ {
		//保证和上一次枚举的元素不相等
		if i > 0 && nums[i] == nums[i-1] {
			continue
		}
		//使用双指针枚举b和c
		j, k := i+1, n-1
		for j < k {
			sum := nums[i] + nums[j] + nums[k]
			//如果和为target直接返回
			if sum == target {
				return target
			}
			update(sum)

			//如果和大于target
			if sum > target {
				//移动c对应的指针
				k0 := k - 1
				//去重，移动到下一个不相等的元素
				for j < k0 && nums[k0] == nums[k] {
					k0--
				}
				k = k0
			} else {
				//如果和小于target,则移动b对应的指针
				j0 := j + 1
				for j0 < k && nums[j0] == nums[j] {
					j0++
				}
				j = j0
			}
		}
	}
	return best
}
